package com.ruben.leetCode;/**
 * @ClassName: Solution
 * @Date: 2020/10/17 0017 23:23
 * @Description:
 */

import java.util.HashSet;
import java.util.Set;

/**
 * @ClassName: TotalNQueensSolution
 * @Description: 我还没有写描述
 * @Date: 2020/10/17 0017 23:23
 * *
 * @author: <achao1441470436@gmail.com>
 * @version: 1.0
 * @since: JDK 1.8
 */
public class TotalNQueensSolution {

    public static void main(String[] args) {
        System.out.println(totalNQueens(4));
    }

    public static int totalNQueens(int n) {
        Set<Integer> columns = new HashSet<>();
        Set<Integer> rightUpToLeftDown = new HashSet<>();
        Set<Integer> leftUpToRightDown = new HashSet<>();
        return ruben(n, 0, columns, rightUpToLeftDown, leftUpToRightDown);
    }

    /**
     * @MethodName: ruben
     * @Description: 我还没有写描述
     * @Date: 2020/10/17 0017 23:34
     * *
     * @author: <achao1441470436@gmail.com>
     * @param: [n 输入的值, row 当前列, columns 出现过的旗子所在的列, rightUpToLeftDown 右上到左下的坐标和, leftUpToRightDown 右上到左下的坐标差]
     * @returnValue:
     */
    public static int ruben(int n, int row, Set<Integer> columns, Set<Integer> rightUpToLeftDown, Set<Integer> leftUpToRightDown) {
        // 当列等于行的时候，一种方案就出来了
        if (row == n) {
            return 1;
        } else {
            // 方案数
            int count = 0;
            // n*n大小的棋盘,为0到n-1
            // 此时这个for循环为第一列
            for (int i = 0; i < n; i++) {
                // 判断是否在同一行中存在过，这里可以用i表示行和第几个旗子
                if (columns.contains(i)) {
                    // 存在就continue
                    continue;
                }
                // 判断是否在右上到左下的斜线中出现过
                // 右上到左下的坐标(0,2) (1,1) (2,0)，他们的x+y都是相等的
                // 当前位置的右上到左下的斜线的x+y等于现在坐标的x+y
                int xySum = i + row;
                if (rightUpToLeftDown.contains(xySum)) {
                    // 存在就continue
                    continue;
                }
                // 判断是否在左上到右下的斜线中出现过
                // 同理，左上到右下的坐标(0,1) (1,2) (2,3)，他们的差都是相等的
                // 当前位置的左上到右下的斜线x-y等于现在坐标的x-y
                int xySub = i - row;
                if (leftUpToRightDown.contains(xySub)) {
                    // 存在就continue
                    continue;
                }
                // 如果都不存在，此时就是我们的旗子所设置的地方
                // 这里要首先把行记录下来
                columns.add(i);
                // 然后把右上到左下的 坐标和 记录下来
                rightUpToLeftDown.add(xySum);
                // 然后把左上到右下的 坐标差 记录下来
                leftUpToRightDown.add(xySub);
                // 旗子设置好了一个，此时并没有结束，还有n-1个，我们开始的row(列)是0,现在需要递归到下一列
                // 把方案总数统计一下
                count += ruben(n, row + 1, columns, rightUpToLeftDown, leftUpToRightDown);
                // 计算完需要从棋盘中移除，便于计算下一种方案
                columns.remove(i);
                rightUpToLeftDown.remove(xySum);
                leftUpToRightDown.remove(xySub);
            }
            // 在整个棋盘遍历完成后返回方案数
            return count;
        }
    }
}
